#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

void SLPrint(SListNode* phead)
{
	SListNode* pcur = phead;
	while(pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

static SListNode* SListNodeBuy(SLDatatype x)
{
	SListNode* newcode = (SListNode*)malloc(sizeof(SListNode));
	if (newcode == NULL)
	{
		perror("malloc newcode");
		exit(1);
	}
	newcode->data = x;
	newcode->next = NULL;
	return newcode;
}

void SLPushBack(SListNode** pphead, SLDatatype x)
{
	assert(pphead);	//指向链表第一个元素的指针的地址肯定不能为NULL
	SListNode* newcode = SListNodeBuy(x);
	if (*pphead == NULL)	//如果是空，直接让头指针指向newcode
	{
		*pphead = newcode;
	}
	else		//如果不是空，则需要找尾
	{
		SListNode* ptail = *pphead;
		while (ptail->next)	//当跳出循环的时候，ptail一定指向最后一个链表的元素
		{
			ptail = ptail->next;
		}
		ptail->next = newcode;
	}
}

void SLPushFront(SListNode** pphead, SLDatatype x)
{
	assert(pphead);
	SListNode* newcode = SListNodeBuy(x);
	newcode->next = *pphead;	//如果原链表不为空，满足；如果原链表为空，相当于newcode->next = NULL，也满足
	*pphead = newcode;	//这一步的意义是直接改变实参的链表结构体指针，让其头指针指向现在最新的元素newcode
}

void SLPopBack(SListNode** pphead)
{
	assert(pphead && *pphead);	//必须要有元素删除，所以*pphead也不能为空
	//如果只有一个元素
	if ((*pphead)->next == NULL)	//注意->操作符的优先级比*高，所以必须打括号
	{
		free(*pphead);
		*pphead = NULL;
	}
	//如果有多个元素 prev ptail NULL
	else
	{
		SListNode* prev = *pphead;
		SListNode* ptail = *pphead;
		while (ptail->next)
		{
			prev = ptail;	//注意顺序prev在尾ptail的前一个
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}

void SLPopFront(SListNode** pphead)
{
	assert(pphead && *pphead);
	SListNode* del = *pphead;
	*pphead = (*pphead)->next;	//如果只有一个节点，那*pphead会指向NULL，满足条件
	free(del);
	del = NULL;
}

SListNode* SLFind(SListNode* phead, SLDatatype val)	//如果存在返回含有该数据的结点指针，如果不存在返回NULL
{
	//可以不进行assert(phead)断言，因为找不到返回NULL就好了
	SListNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == val)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

void SLFrontInsert(SListNode** pphead, SListNode* pos, SLDatatype x)
{
	assert(pphead && *pphead);	//这里*pphead也不能为空，是因为函数的目的是在指定位置之前插入。如果为空就谈不上指定位置了。
	assert(pos);
	SListNode* prev = *pphead;
	if (prev == pos)	//如果满足这个条件说明要插入的位置是pos头节点之前，直接用头插
	{
		SLPushFront(pphead, x);
	}
	else
	{
		SListNode* newcode = SListNodeBuy(x);
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//跳出循环说明此时prev在pos的前一个
		//此时应该正确连接 prev newcode pos
		//注意连接顺序①newcode->pos ②prev->newcode 其实这个顺序没有什么关系，但是这样写保持良好的习惯
		newcode->next = pos;
		prev->next = newcode;
	}
}

void SLBackInsert(SListNode** pphead, SListNode* pos, SLDatatype x)
{
	assert(pphead && *pphead);	//这里*pphead也不能为空，是因为函数的目的是在指定位置之后插入。如果为空就谈不上指定位置了。
	assert(pos);
	SListNode* newcode = SListNodeBuy(x);
	//注意连接顺序①newcode--pos->next ②
	newcode->next = pos->next;
	pos->next = newcode;
}

void SLBackInsert1(SListNode* pos, SLDatatype x)
{
	assert(pos);
	SListNode* newcode = SListNodeBuy(x);
	newcode->next = pos->next;
	pos->next = newcode;
}

void SLDelete(SListNode** pphead, SListNode* pos)
{
	assert(pphead && *pphead);	//*pphead也不能为空，如果为空那就谈不上删除了
	assert(pos);
	SListNode* prev = *pphead;
	if (prev == pos)	//满足此条件，说明要删除的结点是头节点*pphead，直接用头删
	{
		SLPopFront(pphead);
	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//当跳出循环的时候，prev一定在pos的前一个位置
		//注意正确的连接顺序
		//①prev——pos->next ②释放pos
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

void SLDeleteAfter(SListNode* pos)
{
	assert(pos && pos->next);	//pos之后也必须要有节点才可以删除！
	SListNode* pcur = pos->next;
	pos->next = pos->next->next;
	free(pcur);
	pcur = NULL;
}

void SLDestroy(SListNode** pphead)
{
	assert(pphead && *pphead);	//*pphead为空时表示链表为空，链表为空自然就不用销毁了
	SListNode* pcur = *pphead;
	SListNode* del = *pphead;
	while (pcur)
	{
		pcur = pcur->next;
		free(del);
		del = pcur;
	}
	*pphead = NULL;
}